import re
import sys
import math
import random
sys.dont_write_bytecode = False
from the import *

floor = math.floor

def demo(f=None,demos=[]): 
  if f: demos.append(f); return f
  for d in demos: 
    print '\n--|',d.func_name,'|','-'*40,'\n',d.__doc__,'\n'
    d()

def test(f=None,tests=[]): 
  if f: tests.append(f); return f
  ok=no=0
  for t in tests: 
    txt = t.func_name + ' : ' + str(t.__doc__)
    for want,got in  t():
      if want == got:
        ok += 1; print "PASS :",txt
      else:
        no += 1; print "FAIL  :",txt,"!!!!!!"
  if tests:
    print '\n# Final score = %s/%s = %s%% PASSED' \
            % (ok,(ok+no),round(100*ok/(ok+no)))

any   = random.uniform
normal= random.gauss
seed  = random.seed

def one(lst): 
  return lst[  int(any(0,len(lst) - 1)) ]

@test
def oneX():
  "random number generation"
  seed(1)
  return [(sorted([int(any(1,10)) for _ in xrange(10)]), \
               [1, 1, 2, 3, 5, 5, 6, 7, 8, 8])]

def l2s(lst,before="",after="",between="\n"):
  return before +  \
         between.join([str(x) for x in lst]) + \
         after

def pairs(lst):
  x= lst[0]
  for y in lst[1:]:
    yield x,y
    x = y

def div(x,lo,hi,b=10):
  tmp = (x - lo) * 1.0 / ((hi - lo)*1.0/ b)
  return 1 + int(min(b-1, floor(tmp)))

def percentiles(lst0,bins=The.bins) :
   lst = sorted([x for x in lst0 if x != The.skip])
   n    = len(lst)
   d    = max(1,int(n/bins))
   start,stop,out = 0, 0, []
   while stop  < (n - 1): 
     start, stop  = stop, stop+d  
     while stop < n - 1 and lst[stop-1] == lst[stop]:
        stop += 1
     out.append(lst[min(stop, n - 1)])
   return out

def bins(a,bins,key=lambda x,n:x[n]) :
   n    = len(a)
   d    = max(1,int(n/bins))
   start,stop,out = 0, 0, []
   while stop  < (n - 1): 
     start, stop  = stop, stop+d  
     while stop < n - 1 and \
           key(a,stop-1) == key(a,stop):
        stop += 1
     i,j = start, min(stop,n - 1)
     out.append(a[i:j])
   if len(out[-1]) < d*0.5:
     out[-2] += out[-1]
     out.pop()
   return out

def bin(val,breaks, ninf = -2e32) :
  if val == nothing: return val
  before, last = ninf, 0
  for i,now in enumerate(breaks) :
    if val > before and val <= now: return i
    before, last  = now, i
  return last+1  

@test
def percentilesX():
  "divide 100,000 nums into 5 bins"
  seed(1)
  nums = [int(100*any(0,1)**3) for _ in xrange(10**5)]  
  return  [(percentiles(nums),
           [1, 8, 25, 58, 99])]

def lines(file=None,bad=r'(["\' \t\r\n]|#.*)',sep=','):
  """Read lines, kill 'bad' chars, divide on 'sep'"""
  def line1(str):
    str = re.sub(bad,"",str)
    if str:
      return re.sub(bad,"",str).split(sep)
  if file: 
    for line in open(file):
      line = line1(line)
      if line: yield line
  else:
    while True:
      try:
        line = line1(raw_input(""))
        if line: yield line
      except (EOFError):
	      break

class A:
    def __init__(i, **entries): i.__dict__.update(entries)
    def __repr__(i):
      args = ['%s=%s' % (k, repr(v)) 
                for (k,v) in vars(i).items() 
                   if not "_" in k]
      return '<%s>' % ', '.join(args)

def make(inits=None, x=None):
  x     = x     if x     else A()
  inits = inits if inits else {}
  x.__dict__.update(inits)
  return x

def contents(*lsts):
  for lst in lsts:
    for item in lst:
      yield item

def asNum(n):
  if n == The.skip : return n,True
  try              : return float(n),True
  except ValueError: n,False

def asAny(x):
  try: return int(x)
  except ValueError:
    try: return float(x)
    except ValueError:
      return '"' + str(x) + '"'

def oops(*msg) :
  print '#W> ' + ' '.join([str(x) for x in msg])
  The.patience  -= 1
  if The.patience < 0:
    sys.exit('too many errors')

def prin(x):
  sys.stdout.write(x)

class Dict():
    def __init__(i, factory):
        i.factory  = factory
        i.contents = {}
    def __getitem__(i, key):
        if not key in i.contents:  
          i.contents[key] = i.factory(key)
        return i.contents[key]

cvalues = {95 :  
           [ (1   , 12.70) ,
             (3   ,  3.1820) ,
             (5   ,  2.5710) ,
             (10  ,  2.2280) ,
             (20  ,  2.0860) ,
             (80  ,  1.99)   ,
             (320 ,  1.97)]  
           ,99 : 
           [ (1   , 63.6570) ,
             (3   ,  5.8410) ,
             (5   ,  4.0320) ,
             (10  ,  3.1690) ,
             (20  ,  2.8450) ,
             (80  ,  2.64)   ,
             (320 ,  2.58)]
}
def cvalue(n, conf=95):
  vals = cvalues[conf]
  if n > vals[-1][0]:
    return vals[-1][1]
  for (lo,v1),(hi,v2) in  pairs(vals):
    if lo <= n and n < hi:
      return v1 + (n - lo)*1.0/(hi - lo) * (v2 - v1)

from scipy import stats
#http://www.itl.nist.gov/div898/handbook/eda/section3/eda353.htm

def ttest(a,b,conf=95):
  p=stats.ttest_ind(a,b)
  return p[1] < 

def ttestX(a=2):
  lst1= [1,2,3,4,5,6]
  lst2= [x*a for x in lst1]
  return ttest(lst1,lst2)
  
  
